package offer;

import java.util.Deque;
import java.util.LinkedList;

public class Solution31 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n1 = pushed.length, n2 = popped.length;
        if (n1 == 0) {
            return true;
        }
        Deque<Integer> stack = new LinkedList<>();
        int pop = 0, next = 0;
        while (pop < n2) {
            if (!stack.isEmpty() && stack.peek() == popped[pop]) {
                stack.pop();
            } else {
                int i = next;
                while (i < n1 && pushed[i] != popped[pop]) {
                    stack.push(pushed[i]);
                    i++;
                }
                if (i >= n1) {
                    return false;
                }
                next = i + 1;
            }
            pop++;
        }
        return true;
    }
}
